The present invention relates to Asynchronous Transfer Mode (ATM) networks, and in particular to a method and apparatus to compute and sort the timestamps in a system for scheduling packets in Asynchronous Transfer Mode networks for guaranteeing data transfer rates to data sources and data transfer delays from data sources to destinations.
In ATM systems and networks, an important objective is to minimize the complexity involved in the implementation of per-Virtual-Connection (per-VC) schedulers, and to minimize the cost differential of systems including such schedulers with respect to systems using less sophisticated scheduling. More particularly, the minimization of the implementation cost of per-VC schedulers which achieve near-optimal delay and fairness properties in approximating the Generalized Processor Sharing (GPS) policy is a central issue in next-generation ATM switches.
Among GPS-related scheduling disciplines, the class of Packet-by-packet Rate-Proportional Servers (P-RPS) has optimal delay properties. Several well-known scheduling algorithms, such as Packet-by-packet Generalized Processor Sharing (P-GPS), Virtual Clock, Frame-based Fair Queuing (FFQ), and Starting-Potential Fair Queuing (SPFQ), are P-RPS. They differ in the specific function used as system potential, interchangeably referred to as virtual time, which tracks the amount of work that is done by the server and is used to compute, for each cell in the system, a timestamp or finishing potential which specifies when the cell should be transmitted relative to other cells.
While the delay bounds guaranteed by a scheduler are generally accepted as the single measure of interest to characterize its delay properties, two distinct measures of fairness are used.
The Service Fairness Index (SFI), introduced by Golestani as described in S. J. Golestani, “A Self-Clocked Fair Queuing Scheme for Broadband Applications”, PROCEEDINGS OF INFOCOM 94, pp. 636-646, April 1994; captures the distance of the scheduler from the ideal fairness of GPS in distributing service to connections that are simultaneously backlogged. The Worst-case Fairness Index (WFI), defined by Bennett and Zhang in J. C. R. Bennett and H. Zhang, “Hierarchical Packet Fair Queuing Algorithms”, PROCEEDINGS OF SIGCOMM 96, pp. 143-156, Aug. 1996; measures the maximum amount of time that a backlogged connection may have to wait between two consecutive services. Schedulers with minimal WFI are called worst-case-fair schedulers. The achievement of worst-case-fairness is rather desirable, since the distribution of service to competing connections in a scheduler with small WFI is much less bursty than in a scheduler with large WFI.
With P-RPS schedulers, worst-case fairness is achieved by using the Smallest Eligible Finishing potential First (SEFF) cell-selection policy. With the SEFF policy, the scheduler grants the next service to the cell having the minimum timestamp among those which satisfy the eligibility condition, i.e., those cells whose starting potentials are not greater than the current value of system potential. For each connection, the eligibility condition needs to be verified only for the cell at the head of the corresponding queue, since this is the cell with the minimum starting potential among all cells in that queue. Depending on the specific P-RPS, the resulting scheduler may be work-conserving (P-GPS and SPFQ) or non-work-conserving (Virtual Clock and FFQ).
Any P-RPS scheduler using the SEFF selection policy achieves optimal delay bounds, is worst-case fair, and has an SFI very close to the theoretical lower bound in packet-by-packet servers. Because of their near-optimal delay and fairness properties, worst-case-fair P-RPS schedulers have gained popularity, and considerable attention has been devoted to simplifying their implementation. Four factors contribute to the total implementation cost of a worst-case-fair P-RPS. One factor is the complexity of maintaining the system-potential function, and is scheduler-specific. For a scheduler supporting V connections, this complexity is O(V) in P-GPS, O(log V) in SPFQ, and O(1) in Virtual Clock and FFQ. The other three contributions, which are common to all worst-case-fair P-RPS, are (i) the complexity of identifying the eligible cells, (ii) the cost of handling and storing the timestamps, and (iii) the complexity of sorting the timestamps of the eligible cells in order to select the one with the minimum timestamp for the next service.
The complexity of implementing the SEFF policy is a considerable burden when the scheduler's implementation is based on conventional priority queues, since a worst-case of O(V) cells may become eligible at the same time. To solve this problem, Bennett et al. have introduced, in J. C. R. Bennett, D. C. Stephens, and H. Zhang, “High Speed, Scalable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks”, PROCEEDINGS OF ICNP 97, pp. 7-14, October 1997; a simplified scheduling structure, referred to as the discrete-rate scheduler, which can be used when the system is only required to support a relatively small discrete set of guaranteed service rates at any time, an assumption that is certainly realistic in most, if not all, ATM switches.
In the discrete-rate scheduler, backlogged connections with the same service rate are grouped together in a rate First-In-First-Out (FIFO) queue, and scheduling is performed only among the connections at the head of each rate FIFO queue. Thus, the number of connections for which the eligibility condition must be checked and the number of timestamps to be sorted at every timeslot is greatly reduced, to be equal to the number of supported rates. In addition, the complexity of implementing the SEFF policy is considerably decreased. In the case of a worst-case-fair P-RPS, this discrete-rate approach only introduces a negligible degradation in delay bounds, and conserves both the minimal WFI and the excellent SFI of the same P-RPS implemented with conventional priority queue. In order to implement a scheduler with near-optimal delay bounds, the discrete-rate approach requires that the scheduler under consideration be worst-case fair. However, the total implementation cost of the resulting discrete-rate scheduler is not only dramatically lower than that of worst-case-fair schedulers implemented with conventional priority queues, but is even competitive with the cost of non-worst-case-fair schedulers implemented with other known techniques. The competitive cost, together with the achievement of worst-case fairness, explains the recent popularity of the discrete-rate approach for the implementation of P-RPS schedulers.
The discrete-rate scheduler described in J. C. R. Bennett, D. C. Stephens, and H. Zhang, “High Speed, Scalable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks”, PROCEEDINGS OF ICNP 97, pp. 7-14, October 1997; although constitutes an important improvement in reducing the implementation complexity of worst-case-fair P-RPS schedulers, still requires computing and storing a timestamp for each connection, which is a significant contribution to the cost of the scheduler. For convenience as described herein, the scheduling architecture presented in J. C. R. Bennett, D. C. Stephens, and H. Zhang, “High Speed, Scalable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks”, PROCEEDINGS OF ICNP 97, pp. 7-14, October 1997; is referred to as the discrete-rate scheduler with per-connection timestamps.
To further reduce implementation complexity, in F. M. Chiussi and A. Francini, “Implementing Fair Queuing in ATM Switches: The Discrete-Rate Approach”, PROCEEDINGS OF INFOCOM 98, pp. 272-281, March 1998; a discrete-rate scheduler is presented which does not require the computation and storage of a timestamp per connection and only maintains a single timestamp per rate. This no-per-connection-timestamp scheduler still achieves near-optimal delay bounds and is worst-case fair. However, the price paid for the elimination of the per-connection timestamps is that the SFI is compromised.
Another variation of the discrete-rate scheduler, presented in F. M. Chiussi and A. Francini, “A Low-Cost Architecture for the Implementation of Worst-Case-Fair Schedulers in ATM Switches”, PROCEEDINGS OF GLOBECOM 98, November 1998; does not require a whole timestamp per connection, but only uses a single bit per connection, plus one timestamp per rate FIFO queue. The single-bit-timestamp scheduler achieves near-optimal delay bounds, and fairness indices (both SFI and WFI) that are identical to those of the discrete-rate scheduler with per-connection timestamps.
Such discrete-rate schedulers and their implementations are further described in commonly assigned U.S. patent application Ser. No. 09/247,742, filed Feb. 9, 1999; U.S. patent application Ser. No. 09/247,779, filed Feb. 9, 1999; and U.S. patent application Ser. No. 09/432,976, filed Nov. 3, 1999, each of which are incorporated herein by reference.